1. Field of the Invention
This invention relates to a technique for searching for a motion vector, which expresses from which position in other moving-video images a pixel block in a certain moving-video image has moved, being used in video-encoding algorithms, such as MPEG1, MPEG2, and H261, H263, etc., which are international standard.
This specification is based on the patent application No. Hei 9-159964 filed in Japan, the contents of which is incorporated herein by reference.
2. Description of the Related Art
Hereafter, with reference to some typical diagrams, various kinds of conventional motion vector searching methods will be explained. FIG. 1 shows exemplarily a template 1 which is the object which is searched for a motion vector, and a search area 2 which is a search range of the motion vector. In FIG. 1, the template 1 is a pixel block in a certain image and the search area 2 is a pixel block in another image, which is larger than the template 1. The symbols .DELTA.3 denote the pixels which comprise the template 1, and the symbols O4 are the pixels which comprise the search area 2.
In FIG. 1, since a template 1 is superimposed on the search area 2, the pixels O4 of the overlapped part in the search area is not shown. In addition, hereafter, the unit of the number of horizontal pixels is defined as a "pixel," and the unit of the number of perpendicular pixels is called a line. Therefore, the template 1 shown in FIG. 1 is 4-pixel.times.(by) 4-line, and the search area 2 is 11-pixel.times.11-line.
Now, a "whole searching method," which is a first prior art for searching for a motion vector to the template 1, will be explained. By this technique, areas of 4-pixel.times.4-line of the same size with the template 1 are extracted sequentially by one from the search area 2. Between the pixel value of each pixel of this extracted area, and the pixel value of the corresponding pixel in the template 1, sequentially, an absolute difference value or a square difference value, etc., is calculated, and the plural sum-totals of the calculated values for the pixels are calculated for each extracted area.
That is, in the search area 2, over the upper left to the lower right, when the area of 4-pixel.times.4-line is shifted by 1 line or 1 pixel at a time, since the search area 2 has 11-pixel.times.11-line, the total 8.times.8=64 areas are the objects for the operation between the templates 1 (the operation, which calculates a absolute difference value, a square difference value, etc.). And, the motion vector is obtained from the area where the operational result has the minimum result, where this template 1 has moved from.
In FIG. 1, when (0, 0) is set as the motion vector of the pixel block of the position corresponding to the template 1, the range of the value which a motion vector can take is "-4-+3" in both the horizontal direction and the perpendicular direction. Because the template 1 can be transferred to one side by 4 pixels (or 4 lines) and can be transferred to the other side by 3 pixels (or 3 lines), in the horizontal direction and the perpendicular direction, respectively, as understood by referring to FIG. 1.
For example, if the operational value (a sum of absolute difference values, a sum of square difference values, etc.) of an area 5 is the minimum, as shown in FIG. 1, the motion vector is (2, 2). The above is description of the principle to obtain a motion vector. With reference to the typical diagram of FIG. 2, the generalized of this motion vector search is explained.
If the size of a template 6 in a certain image is defined as a-pixel.times.b-line, the size of a search area 7 in another image is defined as c-pixel.times.d-line (c.gtoreq.a, d.gtoreq.b), and the motion vector of the pixel block at the center of the search area 7 which corresponds to the template 6 is defined as "(0, 0)," the ranges of the values which a motion vector can take are "-(c-a)/2 . . . (c-a) /2+1 in the horizontal-direction, and -(d-b)/2 . . . (d-b), 2+1 in the perpendicular-direction," an evaluation of "(c-a+1).times.(d-b+1)" motion vectors. In FIG. 2, the motion vector of the block 8 at the upper-left edge is ((c-a)/2-1 (d-b)/2-1), and the motion vector of the block 9 at the lower-right edge is (-(c-a)/2, -(d-b)/2). Hereinafter, as an example, only the case where a sum of absolute difference values is used as a motion vector searching operational expression for obtaining a motion vector will be explained. Of course, other evaluation formulas, such as a sum of square difference values can be also used as the operational formulas.
Now, if such whole searching methods are adopted, in order to search the search area 2 of FIG. 1, it is required to calculate absolute difference values at 64.times.16=1024 times (by extracting 64 areas, wherein each area consists of 16 pixels). Therefore, the number of operations becomes huge. On the other hand, in order to cut down the number of operations, as a second prior art, a different searching method was proposed, wherein, as first, a motion is evaluated on a reductional image obtained by subsampling, next, a search is conducted only in a narrow range by using the motion vector obtained as the evaluation result as initial value.
With reference to the typical diagram of FIG. 3, this technique will be explained. FIG. 3 exemplarily shows the pixels which are subsampled, when subsampling one pixel per 2-pixel.times.2 lines. The symbol .tangle-solidup.10 and the symbol .circle-solid.11 show the pixels by which subsampled from the template 1 and the search area 2, respectively.
First, when obtaining reductional images by subsampling and searching the range of "-1 . . . +1" of the neighborhood of the initial value on the original image, 16.times.4=64 times of the calculation of absolute difference values (by extracting 16 areas wherein each area consists of 4 pixels) are required on the reductional images, and next 9.times.16=144 times of absolute difference values are required on the original image. Therefore, the sum total of the number of operations becomes 208 times (64+144 times), and the number of operations is sharply cut down compared with the whole searching methods. Such a motion vector searching method using such a reductional image is described, for instance, in "N. Hayasi, T. Kitui, L. Tamitani, H. Honma, Y. Ooi, T. Miyazaki, K. OobuchI;" "A bidirectional motion compensation LSI with a compact motion estimator," IEICE Trans. Electron, E78-C, 12, pp.1682-1690, December 1995, etc. In order to realize the vast searching range as an extension of the above-mentioned technique, it can be also thought that searching is conducted on reductional images whose resolution is further lowered by subsampling one pixel per 4-pixel.times.2-line one pixel per 4-pixel.times.4-line.
A moving-video image consists of two or more images which continued in a time domain. In case that a motion vector is needed to be obtained between the images which are separated in a time domain, the search must be conducted in a relatively wide range since the range to be searched becomes wide. In such a case, in order to cut down the number of operations, the telescopic-search method is proposed as the third prior art.
With reference to the typical diagram in FIG. 4, this telescopic-search method will be explained. In FIG. 4, images 12, 13, 14, and 15 are 4 images which continue in a time domain, the image 15 is the present image, and the image 12, the image 13, and the image 14 are the previous images of 3 screens before, 2 screens before, and 1 screen before, respectively. A rectangle block 16 moves to the image 13 from the image 12 by a motion vector mv1. Similarly, the block 16 moves to the image 14 from the image 13 and moves to the image 15 from the image 14 by motion vectors mv2 and mv3, respectively. At this time, the motion vector of the rectangle block 16 to the image 15 from the image 12 is "mv1+mv2+mv3." By the telescopic-search method, in order to obtain the motion vector from the image 12 to the image 15, an area 17 in the image 14 is searched first, using the rectangle block 16 in the image 15 as a template, and the motion vector mv3 is detected. At this time, the motion vector of the center of the area 17 is (0, 0).
Next, by searching an area 18 in the image 13, the motion vector mv2 is detected. When taking the motion vector from the image 14 to the image 15 of the rectangle block 16 into consideration, the motion vector of the center of the area 18 is mv3. Finally, by searching an area 19 in the image 12, and the motion vector mv1 is detected. When also taking the motion vector from an image 13 to the image 14 of the rectangle block 16 into consideration, the motion vector of the center of an area 19 is "mv3+mv2."
Thus, in this third prior art, the searching for a motion vector is conducted in narrow areas among adjoining images, and the searching for the motion vector in the narrow area in the following adjoining image is conducted by using the detected vector as an initial value, in order to search for the motion vector between the images which separate in a time domain. In addition, in order to cut down the number of operations, combining the sampling method and the telescopic-search method was also proposed. Such a method is described in K. Suguri, T. Minami, H. Matuda, R. Kusaba, T. Kondo, R. Kasai, T. Watanabe, H. Sato, N. Shibata, Y. Tashiro, T. Izuoka, A. Shimiz, H. Kotera, "A real-time motion estimation and compensation LSI with wide search range for MPEG2 video encoding, "IEEE J.Solid-State Circuits, vol. 31, no. 11, pp.1733-1741 November 1996."
However, although a whole searching method whose searching accuracy was the highest, it was not possible accurately to obtain a motion vector even by that method. Hence, if searching the wide searching range in order to improve the quality of the image of a big motion, when the image of a small motion and the image of a big motion are intermingled, it causes incorrect detections in the image of a small motion and the probability that a motion vector cannot be correctly obtained becomes high.
Moreover, even when a template and the block of its perimeter are the images which carry out a transaction (a parallel transfer) in a fixed direction, incorrect detection of a motion vector happens because of a noise, etc. Therefore, there was a problem that the motion vector of the template and the block of its perimeter did not become the same, as a result of search processing (hereinafter, it is expressed as "motion vector varying (or dispersing)," suitably). The dispersion in this motion vector causes a decline in the coding efficiency, and will cause degradation of the quality of the image of a moving-video image.
When a subsampling method or a telescopic-search method is used in order to cut down the number of operations and to make the search range wider furthermore, by the former, a decline in the detection accuracy by pixel thinning out is caused inevitably, and by the latter, once incorrect detection occurs, in order to perform the following search based on the motion vector which is incorrect-detected, an exact motion vector cannot be obtained. By both, the probability that the dispersion in motion vectors occurs was still large than whole searching methods.